package dfs;


/**
 * https://leetcode.cn/problems/word-search/?favorite=2cktkvj
 */
public class _79_单词搜索 {

    char[][] b;

    char[] w;

    public boolean exist(char[][] board, String word) {
        this.b = board;
        this.w = word.toCharArray();

        int row = board.length;
        int col = board[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean crossIndex(int x, int y) {
        if (x < 0 || x >= b.length || y < 0 || y >= b[0].length) return false;

        return true;
    }


    private boolean dfs(int x, int y, int index) {
        // 满足条件
        if (b[x][y] == w[index] && index == w.length - 1) return true;

        // 不符合条件
        if (b[x][y] != w[index]) return false;

        // 防止搜索往回走，先随机给该char[][]数组设置一个非字母的字符
        char tmp = b[x][y];
        b[x][y] = '0';

        if (crossIndex(x - 1, y) && dfs(x -1, y, index + 1)) return true;
        if (crossIndex(x + 1, y) && dfs(x + 1, y, index + 1)) return true;
        if (crossIndex(x, y - 1) && dfs(x, y - 1, index + 1)) return true;
        if (crossIndex(x, y + 1) && dfs(x, y + 1, index + 1)) return true;

        b[x][y] = tmp;

        return false;
    }
}
